package a08_回溯算法;

/**
 * <p>
 * a21_解数独复习1
 * </p>
 *
 * @author flyduck
 * @since 2025/1/7
 */
public class a21_解数独复习1 {
    public void solveSudoku(char[][] board) {
        traversal(board);
    }

    private boolean traversal(char[][] board){
        //每次递归找到为.的格式，然后用1-9去试
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                if(board[i][j] == '.'){
                    for(char k = '1';k <= '9';k++){
                        if (isValid(board, i, j, k)) {
                            board[i][j] = k;//k可以，放到此处
                            boolean result = traversal(board);//继续处理下一个为.的格子
                            if (result) {
                                return result;
                            }
                            board[i][j] = '.';
                        }
                    }
                    //1-9都试了都不行，让调用者去回溯board[i][j] = '.'
                    return false;
                }
            }
        }
        //全部赋值了
        return true;
    }

    private boolean isValid(char[][] board,int rowIdx,int colIdx,char target){
        int n = board.length;

        //行
        for (int i = 0; i < n; i++) {
            if(i == colIdx){
                continue;
            }
            if(board[rowIdx][i] == target){
                return false;
            }
        }

        //列
        for (int i = 0; i < n; i++) {
            if(i == rowIdx){
                continue;
            }
            if(board[i][colIdx] == target){
                return false;
            }
        }

        //9宫格
        for (int i = (rowIdx/3) * 3; i < (rowIdx/3) * 3 + 3; i++) {
            for (int j = (colIdx/3) * 3; j < (colIdx/3) * 3 + 3; j++) {
                if(i == rowIdx && j == colIdx){
                    continue;
                }
                if(board[i][j] == target){
                    return false;
                }
            }
        }
        return true;
    }
}
